
#ifndef LISTA_COMPRIMIDA_H
#define LISTA_COMPRIMIDA_H

#include <iostream>
#include <cassert>
#define DEBUG
using namespace std;

typedef unsigned int Nat;


//se puede asumir que el tipo T tiene constructor por copia
//y operator==
//no se puede asumir que el tipo T tenga operator=
template<typename T>
class ListaComprimida{
public:

	/* constructor por defecto, crea una lista vacia*/
	ListaComprimida();

	/* constructor por copia, una vez copiada, ambas listas deben ser
	 * independientes, es decir, cuando se borre una no debe morir la otra.
	 */
	ListaComprimida(const ListaComprimida<T>& otra);

	/* Constructor que genera una lista con n copias del elemento e.
	 * PRE: n > 0
	 */
	ListaComprimida(Nat n, const T& e);

	/* Destructor. Acordarse de liberar toda la memoria!*/
	~ListaComprimida();

	/* Devuelve true si las listas son iguales */
	bool operator==(const ListaComprimida<T>& otra) const;

	/* Dice si la lista es vacia.
	 */
	bool esVacia() const;

	/* Devuelve el primer elemento de la lista.  Esta funcion debe ser muy rapida.
	 * PRE: no es vacia la lista.
	 */
	const T& primero() const;

	/* Devuelve el ultimo elemento de la lista.  Esta funcion debe ser muy rapida.
	 * PRE: no es vacia la lista.
	 */
	const T& ultimo() const;

	/* Elimina el primer elemento de la lista. Esta funcion debe ser muy rapida.
	 */
	void fin();

	/* Elimina el ultimo elemento de la lista. Esta funcion debe ser muy rapida.
	 */
	void comienzo();

	/* Elimina los primeros n elementos. Esta funcion debe ser muy rapida cuando
	 * los primeros elementos estan repetidos.  En particular, si los primeros
	 * n elementos de la lista son iguales, la funcion debe tomar tiempo constante
	 */
	void drop(Nat n);

	/* Conserva los primeros n elementos y elimina los siguientes.
	 * Esta funcion debe ser muy rapida cuando los ultimos elementos estan
	 * repetidos.  En particular, si los ultimos long-n elementos de la lista
	 * son iguales, la funcion debe tomar tiempo constante
	 */
	void take(Nat n);

	/* Agrega un elemento al inicio de la lista.  El parametro opcional indica
	 * la cantidad de copias del elemento que se agregan
	 * PRE: n > 0
	 */
	void agregarAdelante(const T& e, Nat n = 1);

	/* Agrega un elemento al final de la lista.  El parametro opcional indica
	 * la cantidad de copias del elemento que se agregan
	 * PRE: n > 0
	 */
	void agregarAtras(const T& e, Nat n = 1);

    /* Elimina todas las apariciones de un elemento.
     */
   void quitarTodos(const T& e);

	/* Muestra la lista en formato |e1,e2,en| por el stream
	 * que recibe como parametro, donde ei es el iesimo elemento de la
	 * lista.
	 * El valor de retorno debe ser el ostream recibido como parametro.
     */
	ostream& mostrar(ostream&) const;

	#ifdef DEBUG
    ostream& mostrarEstructura(ostream& os) const
    {
        Nodo* nodo = cabeza;

        if(cabeza == NULL){
            os << "sinNodos" << endl;
            return os;
        }


        while (nodo != NULL)
        {
            os << "[" << nodo->elem << "|" << nodo->cant << "veces" << "]";

            if(nodo->proximo != NULL && nodo == (nodo->proximo)->anterior)
                os << "<";

            nodo = nodo->proximo;

            if(nodo != NULL)
                os << "-->";
        }

        os << endl;

        return os;
    }

    Nat longuitud() const
    {
        return longitud;
    }
    #endif

private:

    /* Llevo las cuentas de los elementos existentes
     para poder satisfacer la complejidad
    requerida en take*/
    Nat longitud;

    class Nodo
    {
        public:
            T elem;
            Nat cant; // cantidad de repeticiones del elemento
            Nodo* proximo;
            Nodo* anterior;

            /* Dado que no puedo utilizar asignacion para el tipo T
            Debo construirlo por copia en la lista de inicializacion*/
            Nodo(const T& e, const Nat& c, Nodo* prox, Nodo* ant):elem(e)
            {
                cant = c;
                proximo = prox;
                anterior = ant;
            }

            Nodo(const Nodo& otro):elem(otro.elem)
            {
                cant = otro.cant;
                proximo = NULL; // No copia los punteros!
                anterior = NULL;
            }

            /* Devuelve true si los nodos contienen la misma info */
            bool operator==(const Nodo& otro) const
            {
                return  elem == otro.elem && cant == otro.cant;
            }
    };

    // La lista necesita saber donde esta el primero
    Nodo* cabeza;
    // Y tambien necesita conocer el ultimo
    Nodo* cola;

	//No se puede modificar esta funcion.
	ListaComprimida<T>& operator=(const ListaComprimida<T>& otra) {
		assert(false);
	}

};

// Constructores
template<typename T>
ListaComprimida<T>::ListaComprimida()
{
    longitud = 0;
    cabeza = NULL;
    cola = NULL;
}

template<typename T>
ListaComprimida<T>::ListaComprimida(Nat n, const T& e)
{
    longitud = n;

    // Solo un nodo con anterior y proximo en NULL
    Nodo* nodoNuevo = new Nodo(e,n,NULL,NULL);

    cabeza = cola = nodoNuevo;
}

template<typename T>
ListaComprimida<T>::ListaComprimida(const ListaComprimida<T>& otra)
{
    longitud = otra.longitud;

    // Hay algo que copiar?
    if(otra.cabeza == NULL)
    {
        cabeza = cola = NULL;
        return;
    }

    // Hay almenos uno para copiar!
    Nodo* nodoACopiar = otra.cabeza;
    Nodo* nodoCopia = new Nodo(*nodoACopiar); // Copia con anterior y proximo en NULL!

    cabeza = nodoCopia;

    nodoACopiar = nodoACopiar->proximo; // Paso al proximo

    while( nodoACopiar != NULL ) // Mientras halla algo que copiar!
    {
        // Mantengo el puntero al nodo copiado en el ciclo anterior
        Nodo* nodoAntCopiado = nodoCopia;
        // Copio el nodo creando un nuevo espacio en memoria
        nodoCopia = new Nodo(*nodoACopiar);

        // Asigno proximo del anterior y anterior del que estoy copiando.
        nodoAntCopiado->proximo = nodoCopia;
        nodoCopia->anterior = nodoAntCopiado;

        nodoACopiar = nodoACopiar->proximo; // recorro la lista a copiar
    }

    cola = nodoCopia;
    /* El anterior de la cola queda propiamente seteado
     el proximo es NULL por el construct por copia del nodo*/
}

// Destructores
template<typename T>
ListaComprimida<T>::~ListaComprimida()
{
    while(cabeza != NULL)
    {
        Nodo* pAux = cabeza;

        cabeza = cabeza->proximo;

        delete pAux;
    }
}

template<typename T>
bool ListaComprimida<T>::esVacia() const
{
    return cabeza == NULL;
}

template<typename T>
const T& ListaComprimida<T>::primero() const
{
    return cabeza->elem;
}

template<typename T>
const T& ListaComprimida<T>::ultimo() const
{
    return cola->elem;
}

template<typename T>
void ListaComprimida<T>::fin()
{
    if(esVacia())
        return;

    longitud--;

    if(cabeza->cant > 1)
        cabeza->cant--;
    else if (cabeza->proximo != NULL)
    {
        cabeza = cabeza->proximo;

        delete cabeza->anterior;

        cabeza->anterior = NULL;
    }else{
        delete cabeza;
        cabeza = cola = NULL;
    }
}

template<typename T>
void ListaComprimida<T>::comienzo()
{
    if(esVacia())
        return;

    longitud--;

    if(cola->cant > 1)
        cola->cant--;
    else if (cola->anterior != NULL)
    {
        cola = cola->anterior;

        delete cola->proximo;

        cola->proximo = NULL;
    }else{
        delete cola;
        cola = cabeza = NULL;
    }
}

template<typename T>
void ListaComprimida<T>::drop(Nat n)
{

    // Cantidad de elementos que deben eliminarse
    if(n > longitud)
        n = longitud;

    longitud -= n;

    // Mientras hallan cosas por eliminar...
    while(n > 0)
    {
        if (cabeza->cant > n){
            cabeza->cant -= n;
            n = 0;
        }else if (cabeza->cant <= n){

            n -= cabeza->cant;

            if(cabeza != cola){ // No es el ultimo
                cabeza = cabeza->proximo;
                delete cabeza->anterior;
                cabeza->anterior = NULL;
            }else{ // Si es el ultimo
                delete cabeza;
                cabeza = cola = NULL;
            }
        }

    }
}

template<typename T>
void ListaComprimida<T>::take(Nat n){

    // Cantidad de elementos que deben eliminarse
    Nat aEliminar;
    if(n >= longitud)
        aEliminar = 0;
    else{
        aEliminar = longitud - n;
        longitud = n;
    }

    // Mientras hallan cosas por eliminar...
    while(aEliminar > 0)
    {
       if (cola->cant > aEliminar){
            cola->cant -= aEliminar;
            aEliminar = 0;
        }else if (cola->cant <= aEliminar){

            aEliminar -= cola->cant;

            if(cola != cabeza){ // No es el ultimo
                cola = cola->anterior;
                delete cola->proximo;
                cola->proximo = NULL;
            }else{ // Si es el ultimo
                delete cola;
                cabeza = cola = NULL;
            }
        }
    }
}

template<typename T>
void ListaComprimida<T>::agregarAdelante(const T& e, Nat n)
{
    longitud += n;

    if (esVacia()){
        cabeza = new Nodo(e,n,NULL,NULL);
        cola = cabeza;
        return;
    }

    if (cabeza->elem == e) // El elemento a agregar esta primero?
        cabeza->cant += n;   // Aumento la cantidad solamente
    else{
        // Creo el nuevo nodo y le asigno cabeza como proximo
        Nodo* nodoNuevo = new Nodo(e,n,cabeza,NULL);

        //El nodo apuntado por cabeza sera ahora el 2do
        cabeza->anterior = nodoNuevo; // anterior apunta a la nueva cabeza

        cabeza = nodoNuevo; // Asigno el nuevo nodo cabeza!
    }
}

template<typename T>
void ListaComprimida<T>::agregarAtras(const T& e, Nat n)
{
    longitud += n;

    if (esVacia()){
        cabeza = new Nodo(e,n,NULL,NULL);
        cola = cabeza;
        return;
    }

    if (cola->elem == e)
        cola->cant += n;
    else{
        // Creo el nuevo nodo y le asigno cola como anterior
        Nodo* nodoNuevo = new Nodo(e,n,NULL,cola);

        // Habian nodos?
        if (cola != NULL)// El nodo apuntado por cola sera ahora el ante-ultimo,
            cola->proximo = nodoNuevo; //por lo que proximo apunta a la nueva cola

        cola = nodoNuevo; // Asigno el nuevo nodo cabeza!
    }
}

template<typename T>
void ListaComprimida<T>::quitarTodos(const T& e)
{
    Nodo* recorreProx = cabeza; // Recorre proximos desde cabeza
    Nodo* recorreAnt = cola;    // Recorre anteriores desde cola

    while(recorreProx != recorreAnt)
    {
        if(recorreProx->elem == e) // Si es el elemento
        {
            if(recorreProx->anterior == NULL) // Si no hay anterior
            {
                // Debo correr la cabeza
                cabeza = recorreProx->proximo; // (Puede que quede en recorreAnt)
                cabeza->anterior = NULL;

                longitud -= recorreProx->cant; // Corrigo la longitud
                delete recorreProx;

                recorreProx  = cabeza; // Al proximo!
            }else{ // Si habia anterior
                // Puenteo a recorreProx,
                // siempre habra proximo dado que no se toco con recorreAnt
                (recorreProx->anterior)->proximo = recorreProx->proximo;
                (recorreProx->proximo)->anterior = recorreProx->anterior;

                longitud -= recorreProx->cant;

                Nodo* pAux = recorreProx;
                recorreProx = recorreProx->proximo; // Al proximo!

                delete pAux;
            }
        }else // No es el elemento que busco
            recorreProx = recorreProx->proximo; // Solo avanzo

        // recorreProx avanzo por lo que ahora si podrian ser iguales
        if (recorreProx == recorreAnt)
            break; // Si lo son, salgo del while dado que este caso se maneja afuera

        if(recorreAnt->elem == e)
        {
            if(recorreAnt->proximo == NULL) // Si no hay proximo
            {
                // Debo correr la cola
                cola = recorreAnt->anterior; // (Puede que quede en recorrerProx)

                // El recorreProx pudo haber eliminado ya el anterior de recorreAnt
                if(cola != NULL)
                    cola->proximo = NULL; // Sino seteo bien la cola

                longitud -= recorreAnt->cant; // Corrigo la longitud
                delete recorreAnt;

                recorreAnt = cola; // Al anterior!
            }else{ // Si habia anterior
                // Puenteo a recorreAnt
                (recorreAnt->anterior)->proximo = recorreAnt->proximo;
                (recorreAnt->proximo)->anterior = recorreAnt->anterior;

                longitud -= recorreAnt->cant;

                Nodo* pAux = recorreAnt;
                recorreAnt = recorreAnt->anterior;

                delete pAux;
            }
        }else
            recorreAnt = recorreAnt->anterior;
    }

    // Cuando estan en el mismo nodo
    if(recorreProx->elem == e) // Si es el elemento
    {
        if(recorreProx->proximo == NULL && recorreProx->anterior == NULL)
        {
            // La lista queda vacia!
            cabeza = cola = NULL;
            longitud = 0;
            delete recorreProx;
        }else if(recorreProx->anterior == NULL){ // Muevo solo la cabeza
            cabeza = recorreProx->proximo;
            longitud -= recorreProx->cant;
            delete recorreProx;
        }else if((recorreProx->proximo == NULL)){ // Muevo solo la cola
            cola = recorreProx->anterior;
            longitud -= recorreProx->cant;
            delete recorreProx;
        }else{ // Ambos != NULL
            (recorreProx->proximo)->anterior = recorreProx->anterior;
            (recorreProx->anterior)->proximo = recorreProx->proximo;

            longitud -= recorreProx->cant;

            delete recorreProx;
        }
    }
}

template<typename T>
ostream& ListaComprimida<T>::mostrar(ostream& os) const
{
    os << "[";

    Nodo* nodoAImprimir = cabeza;

    while (nodoAImprimir != NULL)
    {
        for(Nat i = 1;i <= nodoAImprimir->cant; i++)
            if (i == nodoAImprimir->cant && nodoAImprimir->proximo == NULL)
                os << nodoAImprimir->elem;
            else
                os << nodoAImprimir->elem << ",";

        nodoAImprimir = nodoAImprimir->proximo;
    }

    os << "]";

    return os;
}

// operadores
template<typename T>
bool ListaComprimida<T>::operator==(const ListaComprimida<T>& otra) const
{
    Nodo* nodoPropio = cabeza;
    Nodo* nodoComparar = otra.cabeza;

    while(nodoPropio != NULL && nodoComparar != NULL)
    {
        if (!(*nodoPropio == *nodoComparar))
            return false;

        nodoPropio = nodoPropio->proximo;
        nodoComparar = nodoComparar->proximo;
    }

    return nodoPropio == NULL && nodoComparar == NULL;
}

template<class T>
ostream& operator<<(ostream& out, const ListaComprimida<T>& l) {
	return l.mostrar(out);
}

#endif //LISTA_COMPRIMIDA_H

